package Str;

public class Manacher {
    //字符串str中最长回文字子串的长度如何求解
    public static char[] manacherString(String str){
        char[] chars = str.toCharArray();
        char[] res = new char[str.length() * 2+1];
        int index =0;
        for (int i = 0; i != res.length ; i++) {
            //偶数位都赛一个特殊字符
            res[i] = (i & 1) == 0 ? '#':chars[index++];
        }
        return res;
    }
    public static int maxLcpsLength(String s){
        if (s == null || s.length() == 0){
            return  0;
        }
        char[] str = manacherString(s);//1221 -> 1#2#2#1#(加上特殊字符)
        int[] pArr = new int[str.length];
        int c =-1;//中心
        int r = -1;//回文右边界的再往右的一个位置,最右的有效区是R-1位置
        int max = Integer.MIN_VALUE;//扩出来的最大值
        for (int i = 0; i != str.length ; i++) {//每一个位置都求回文半径
            pArr[i] = r > i ? Math.min(pArr[2 * c - i],r-i) : 1;//2*c - i 就是 i'的位置
            //你不用验证,就知道是回文的区域
            /*如果 i 在 R 外 ,1
            * 如果 i 在 R 内 , 俩个瓶颈中 i - R 与 i'的区域的较小值*/
            while (i + pArr[i] < str.length && i - pArr[i] > -1){
                //下面从至少不用验的区域开始扩
                //下面这样写就是为了省代码,俩种不用扩的情况直接退出
                if (str[i + pArr[i]] == str[i - pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if (i +pArr[i] > r){
                r = i +pArr[i];
                c = i;
            }
            max = Math.max(max,pArr[i]);
        }
        //因为找到最大的原串,你还需要除2-1,所以最长的字串就是半径-1(为什么减1本身算1个)
        return max -1;
    }
}
